package com.watson.onebox.algorithm.dijkstra;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
 *
 * */
public class GraphTest {
    private static int edgeNums;   //边的数量
    private static char[] mVexs;   //顶点集合
    private static final int INF = Integer.MAX_VALUE;
    //使用的例子的图片在sample_pic.webp中
    private static int[][] mMatrix = {{0, 10, INF, INF, INF, 11, INF, INF, INF},
            {10, 0, 18, INF, INF, INF, 16, INF, 12},
            {INF, 18, 0, 22, INF, INF, INF, INF, 8},
            {INF, INF, 22, 0, 20, INF, INF, 16, 21},
            {INF, INF, INF, 20, 0, 26, INF, 7, INF},
            {11, INF, INF, INF, 26, 0, 17, INF, INF},
            {INF, 16, INF, INF, INF, 17, 0, 19, INF},
            {INF, INF, INF, 16, 7, INF, 19, 0, INF},
            {INF, 12, 8, 21, INF, INF, INF, INF, 0}
    };    //邻接矩阵

    /**
     * @param vs   起始顶点
     * @param prev 前驱顶点
     * @param dist 最终顶点距离
     */
    public void dijkstra(int vs, int[] prev, int[] dist) {
        boolean[] flag = new boolean[mVexs.length];

        for (int i = 0; i < mVexs.length; i++) {
            flag[i] = false;    //顶点i还没有获取到
            prev[i] = 0;        //顶点i的前驱节点为0
            dist[i] = mMatrix[vs][i];   //顶点i的最短路劲为"顶点vs"到"顶点i"的权重
        }

        //对顶点vs初始化
        flag[vs] = true;
        dist[vs] = 0;

        int k = 0;
        for (int i = 0; i < mVexs.length; i++) {
            int min = INF;

            for (int j = 0; j < mVexs.length; j++) {
                if (flag[j] == false && dist[j] < min) {
                    min = dist[j];
                    k = j;
                }
            }
            flag[k] = true;

            // 修正当前最短路径和前驱顶点
            // 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
            for (int j = 0; j < mVexs.length; j++) {
                int tmp = mMatrix[k][j] == INF ? INF : (min + mMatrix[k][j]);
                if (flag[j] == false && tmp < dist[j]) {
                    dist[j] = tmp;
                    prev[j] = k;
                }
            }
        }

        // 打印dijkstra最短路径的结果
        System.out.printf("dijkstra(%c): \n", mVexs[vs]);
        for (int i = 0; i < mVexs.length; i++)
            System.out.printf("  shortest(%c, %c)=%d\n", mVexs[vs], mVexs[i], dist[i]);
    }


    /**
     * floyd算法
     */
    public static void floyd(int[][] dist) {
        for (int k = 0; k < dist.length; k++) {
            for (int i = 0; i < dist.length; i++) {
                for (int j = 0; j < dist.length; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        // 输出
        for (int i = 0; i < dist.length; i++) {
            System.out.print("节点" + (i + 1) + " 的最短路径");
            for (int j = 0; j < dist.length; j++) {
                System.out.print(dist[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 最小生成树，普里姆(prim)算法
     */
    public static void createMinSpanTreePrim() {
        // 定义一维数组，存放用于比较最小权值的顶点权值，0代表已经比较过
        int[] lowcost = new int[mMatrix.length];

        // 初始化数组为第一个顶点的权值
        System.arraycopy(mMatrix[0], 0, lowcost, 0, mMatrix.length);

        int[] eleNum = new int[mMatrix.length];

        int sum = 0;
        // 循环比较
        for (int i = 0; i < mMatrix.length; i++) {

            // 先比较找出最小的权值节点
            int minIndex = -1;
            for (int j = 0; j < mMatrix.length; j++) {
                if (lowcost[j] > 0 &&
                        lowcost[j] < INF &&
                        (minIndex == -1 || lowcost[minIndex] > lowcost[j])) {
                    minIndex = j;
                }
            }

            // 判断是否全部为0，找不到最小值
            if (minIndex == -1) {
                break;
            }

            System.out.println("访问到了节点：" + minIndex + "，权值：" + lowcost[minIndex]);
            sum += lowcost[minIndex];

            // 将当前节点的值修改成0
            lowcost[minIndex] = 0;
            eleNum[i+1] = minIndex;

            // 将存放最小权值的数组与下一个节点的所有连接点对比，找出最小权值
            for (int j = 0; j < mMatrix.length; j++) {
                if (mMatrix[minIndex][j] < lowcost[j]) {
                    lowcost[j] = mMatrix[minIndex][j];
                }
            }
        }
        System.out.println("最小生成树的权值总和：" + sum);
        System.out.println("输出节点顺序" + Arrays.toString(eleNum));
        System.out.println("输出节点顺序::::" + Arrays.toString(lowcost));
    }

    /**
     * kruskal算法创建最小生成树
     */
    public static void createMinSpanTreeKruskal(List<Edge> edges) {
        // 定义一个一维数组，下标为连线的起点，值为连线的终点
        int[] parent = new int[edges.size()];

        int sum = 0;
        for (Edge edge : edges) {

            // 找到起点和终点在临时连线数组中的最后连接点
            int dst1 = find(parent, edge.getStart());
            int dst2 = find(parent, edge.getEnd());

            // 通过起点和终点找到的最后连接点是否为同一个点，是则产生回环
            if (dst1 != dst2) {

                // 没有产生回环则将临时数组中，起点为下标，终点为值
                parent[dst1] = dst2;
                System.out.println("访问到了节点：{" + edge.getStart() + "," + edge.getEnd() + "}，权值：" + edge.getWeight());
                sum += edge.getWeight();
            }
        }
        for (int value : parent) {
            System.out.println(value + " ");
        }
        System.out.println("最小生成树的权值总和：" + sum);
    }

    /**
     * 获取集合的最后节点
     */
    private static int find(int parent[], int index) {
        while (parent[index] != 0) {
            index = parent[index];
        }
        return index;
    }


    public static void main(String[] args) {
        createMinSpanTreePrim();

        floyd(mMatrix);
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(4, 7, 7));
        edges.add(new Edge(2, 8, 8));
        edges.add(new Edge(0, 1, 10));
        edges.add(new Edge(0, 5, 11));
        edges.add(new Edge(1, 8, 12));
        edges.add(new Edge(3, 7, 16));
        edges.add(new Edge(1, 6, 16));
        edges.add(new Edge(5, 6, 17));
        edges.add(new Edge(1, 2, 18));
        edges.add(new Edge(6, 7, 19));
        edges.add(new Edge(3, 4, 20));
        edges.add(new Edge(3, 8, 21));
        edges.add(new Edge(2, 3, 22));
        edges.add(new Edge(3, 6, 24));
        edges.add(new Edge(4, 5, 26));

        createMinSpanTreeKruskal(edges);
    }
}

